package com.huang.leetcode.DP;

/**
 * @Author：CreateSequence
 * @Date：2020-07-30 20:39
 * @Description：最大子序和
 * 题解：https://leetcode-cn.com/problems/maximum-subarray/solution/hua-jie-suan-fa-53-zui-da-zi-xu-he-by-guanpengchn/
 */
public class PB53 {

    public int maxSubArray(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        int ans = nums[0];
        int sum = 0;
        for (int n : nums) {
            //如果sum是正的，那么下一个数加上sum是趋向变大的
            if (sum >= 0) {
                sum += n;
            } else {
                //否则下一个数加上sum是趋向变小的，舍弃sum
                sum = n;
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }

}
